package org.hw.algorithm;

import org.hw.algorithm.common.CommonUtils;

import java.util.Arrays;

public class demo {
    public static void main(String[] args){
        int[] arr={8,4,6,5,9};
        demo.mergeSort(arr,0,4);
        System.out.println(Arrays.toString(arr));

//        String str1="WQABCSABDSWQE";
//        String str2="ABCSAB";
//        int[] next=kmpNext(str2);
//        System.out.println(Arrays.toString(next));
//        System.out.println(strMatchKmp(str1,str2,next));
    }
    public static void insertSort(int[] arr){
        for (int i=1;i< arr.length;i++){
            for (int j=i;j>0;j--){
                if (arr[j]<arr[j-1]){
                    CommonUtils.swapInt(arr,j,j-1);
                }
            }
        }

    }

    public static void shellSort(int[] arr){
        for (int gap=arr.length/2;gap>0;gap /= 2){
            for (int i=gap;i<arr.length;i++){
                for (int j=i;j>=gap;j-=gap){
                    if (arr[j]<arr[j-gap]){
                        CommonUtils.swapInt(arr,j,j-gap);
                    }
                }
            }
        }
    }

    public static void quickSort(int[] arr, int left, int right){
        if (left<right) {
            int i=left;
            int j=right;
            int pivot=arr[left];
            while(i<j){
                while (i<j && arr[j]>=pivot) j--;
                arr[i]=arr[j];
                while (i<j && arr[i]<=pivot)i++;
                arr[j]=arr[i];
            }
            arr[i]=pivot;
            quickSort(arr,i+1,right);
            quickSort(arr,left,i-1);
        }
    }
    public static void mergeSort(int[] arr,int left,int right){
        if (left<right){
            int mid=left+(right-left)/2;
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
            merge(arr,left,mid+1,right);
        }

    }

    public static void merge(int[] arr,int left,int right,int last){
        int[] tmp=new int[last-left+1];
        int i=left;
        int j=right;
        int k=0;
        while (i<right && j<=last){
            if (arr[i]<arr[j]){
                tmp[k++]=arr[i++];
            }else {
                tmp[k++]=arr[j++];
            }
        }
        while (i<right)tmp[k++]=arr[i++];
        while (j<=last)tmp[k++]=arr[j++];
        for (int m=0;m< tmp.length;m++){
            arr[left+m]=tmp[m];
        }
    }

    public static int strMatchKmp(String str1,String str2,int[] next){
        int len1=str1.length();
        int len2=str2.length();
        for (int i=0,j=0;i<len1;i++){
            while (j>0 && str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if (str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if (j==len2){
                return i-j+1;
            }
        }
        return -1;
    }
    public static int[] kmpNext(String str){
        int[] arr=new int[str.length()];
        for (int i=1,j=0;i<arr.length;i++){
            while (j>0 && str.charAt(i)!=str.charAt(j)){
                j=arr[j-1];
            }
            if (str.charAt(i)==str.charAt(j)){
                j++;
            }
            arr[i]=j;
        }
        return arr;
    }


}
